#define _CRT_SECURE_NO_WARNINGS 1
const int N = 1e5 + 10;
vector<int> prim;
vector<bool> st(N + 10, false);
void get_prim() {
    if (!prim.empty()) return;
    st[0] = st[1] = true;

    st[1] = true;
    for (int i = 2; i < N; i++) {
        if (!st[i])prim.push_back(i);
        for (int j = 0; i <= N / prim[j]; j++) {
            st[prim[j] * i] = true;
            if (i % prim[j] == 0) {
                break;
            }
        }
    }
    return;
}


class Solution {
public:
    int finds(int x, vector<int>& p) {
        if (x != p[x])p[x] = finds(p[x], p);
        return p[x];
    }

    void fun(int a, int b, vector<int>& p, vector<int>& nums) {
        int x = finds(a, p);
        int y = finds(b, p);

        if (x == y)return;
        if (nums[x] > nums[y]) swap(x, y);
        nums[y] += nums[x];
        p[x] = y;

        return;
    }

    long long countPaths(int n, vector<vector<int>>& edges) {

        get_prim();
        st[1] = true;
        vector<int> p(n + 10);
        vector<int> nums(n + 10, 1);
        map<int, vector<int>> mp;
        for (int i = 0; i <= n; i++)p[i] = i, nums[i] = 1;
        int cnt = 0;
        for (int i = 1; i <= 100000; i++) {
            if (!st[i])cnt++;
        }
        cout << cnt << endl;
        for (auto it : edges) {
            // cout<<it[0]<<" "<<it[1]<<" "<<st[it[0]]<<" "<<st[it[1]]<<endl;
            if (!st[it[0]]) {
                if (st[it[1]]) {
                    mp[it[0]].push_back(it[1]);
                }
                else {
                    continue;
                }
            }
            else {
                if (!st[it[1]]) {
                    mp[it[1]].push_back(it[0]);
                }
                else {
                    fun(it[0], it[1], p, nums);
                }
            }
        }
        // for(int i=1;i<=n;i++){
        //     cout<<p[i]<<" "<<nums[i]<<endl;
        // }
        long long ans = 0;
        long long sum1 = 0;
        long long sum2 = 0;
        for (auto it : mp) {
            sum1 = sum2 = 0;
            for (auto son : it.second) {
                son = p[son];
                // cout<<nums[son]<<endl;
                sum1 += (long long)nums[son];
                sum2 += (long long)nums[son] * nums[son];
            }
            cout << sum1 << " " << sum2 << endl;
            ans += sum1 + (sum1 * sum1 - sum2) / 2;
        }
        return ans;
    }
};